1502. Центр масс

 

Найдите координаты центра масс выпуклого многоугольника, вырезанного из дерева.

 

Вход. Состоит из нескольких тестов. Первая строка каждого теста содержит количество вершин n (n ≤ 100) многоугольника. Следующие n пар целых чисел описывают x и y координаты точек. Точки каждого многоугольника не упорядочены. Многоугольник в последнем тесте содержит n < 3 вершин и не обрабатывается.

 

Выход. Для каждого многоугольника в отдельной строке выведите координаты x и y его центра масс с тремя десятичными знаками.

 

Пример входа

Пример выхода

4 0 1 1 1 0 0 1 0

3 1 2 1 0 0 0

7

-4 -4

-6 -3

-4 -10

-7 -12

-9 -8

-3 -6

-8 -3

1

0.500 0.500

0.667 0.667

-6.102 -7.089

 

 

РЕШЕНИЕ

геометрия

 

Анализ алгоритма

Будем считать, что масса равномерно распределена по области, ограниченной многоугольником (то есть фигура вырезана из тонкого однородного материала).

Теорема. Пусть фигура Ф является объединением двух других фигур Ф1 и Ф2, пересекающимися только по границе. Тогда центр тяжести фигуры Ф выражается так:

Xc = , Yc = , где

(Xc, Yc) – координаты центра тяжести фигуры Ф;

(Xc1, Yc1) – координаты центра тяжести фигуры Ф1;

(Xc2, Yc2) – координаты центра тяжести фигуры Ф2;

S – площадь фигуры Ф, S1 – площадь фигуры Ф1, S2 – площадь фигуры Ф2.

 

Кроме того, для треугольника центр тяжести определяется так:

Xc = , Yc = ,

Разобъем многоугольник на треугольники. Для каждого треугольника найдем его центр тяжести (xci, yci) и площадь si. Тогда координаты центра многоугольника можно найти следующим образом:

Xc = , Yc =

Здесь m равно количеству треугольников, на которые разбит многоугольник.

 

Реализация алгоритма

Пусть пара p содержит координаты точки P. Пусть точка О – центр координат. Функция PolarAngle(p) возвращает значение полярного угла между вектором OP и осью OX, измеряемое в пределах от 0 до  радиан.

 

double PolarAngle(pair<double,double> p)

{

  double res = atan2(1.0*p.second,1.0*p.first);

  if (res < 0) res += 2*PI;

  return res;

}

 

Функция f используется при сортировке вершин многоугольника по полярному углу.

 

int f(pair<double,double> a, pair<double,double> b)

{

  return PolarAngle(a) < PolarAngle(b);

}

 

Функция TriangleSquare(a, b, c) вычисляет площадь треугольника, заданного координатами трех вершин.

 

double TriangleSquare(pair<double,double> a, pair<double,double> b,

                      pair<double,double> c)

{

  return abs((b.first - a.first) * (c.second - a.second) –

             (c.first - a.first) * (b.second - a.second)) / 2.0;

}

 

Основная часть программы. Координаты вершин очередного многоугольника запоминаем в векторе пар v.

 

  while(scanf("%d",&n), n > 2)

  {

    v.clear();

    for(i = 0; i < n; i++)

    {

      scanf("%d %d",&a,&b);

      v.push_back(make_pair(a,b));

    }

 

Найдем координаты точки (NewXC, NewYC), лежащей внутри многоугольника. Поскольку по условию задачи многоугольник выпуклый, то в качестве такой точки можно взять центр тяжести треугольника, образованного точками 0, 1 и 2.

 

    NewXC = (v[0].first + v[1].first + v[2].first) / 3.0;

    NewYC = (v[0].second + v[1].second + v[2].second) / 3.0;

 

Совершим параллельный перенос всех точек многоугольника на вектор (–NewXC, –NewYC).

 

    for(i = 0; i < n; i++)

      v[i].first -= NewXC, v[i].second -= NewYC;

 

Теперь начало координат (0, 0) находится внутри выпуклого многоугольника. Сортируем вершины многоугольника по полярному углу.

 

    sort(v.begin(),v.end(),f);

 

Разобъем исходный многоугольник на треугольники с вершинами (0, i, i + 1), . Для каждого такого тругольника вычисляем его площадь в переменной tempSquare, а также координаты его центра. Последние прибавляем к переменным xc и yc, умножая их предварительно на tempSquare. В переменной s накапливаем площадь всего многоугольника.

 

    xc = yc = s = 0;

    for(i = 1; i < n - 1; i++)

    {

      tempSquare = TriangleSquare(v[0],v[i],v[i+1]);

      s += tempSquare;

      xc += tempSquare*(v[0].first + v[i].first + v[i+1].first) / 3.0;

      yc += tempSquare*(v[0].second+v[i].second + v[i+1].second)/ 3.0;

    }

 

Разделив полученные значения xc и yc на s и сдвинув их на вектор (NewXC, NewYC), получим координаты центра масс исходного многоугольника.

 

    xc = xc / s + NewXC; yc = yc / s + NewYC;

 

Выводим координаты центра масс.

 

    printf("%.3lf %.3lf\n",xc,yc);

  }